package written_examination_questions;

import java.util.Stack;

public class Demo20251109 {
    /**
     * 有效的括号
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        char[] ch = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < ch.length; i++) {
            char tmp = ch[i];
            // 左括号直接入栈
            if (tmp == '(' || tmp == '[' || tmp == '{') {
                stack.push(tmp);
            } else {
                // 检验栈是否为空
                if (stack.isEmpty()) return false;
                // 右括号先看是否与栈顶括号匹配，匹配弹出，不匹配返回false
                char top = stack.pop();
                if (top != '(' && tmp == ')' ||
                        top != '[' && tmp == ']' ||
                        top != '{' && tmp == '}') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    /**
     * 水果成篮
     */
    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        int[] hash = new int[n + 1]; // 统计水果种类

        int  ret = 0;
        for (int left = 0, right = 0, kinds = 0; right < n; right++){
            int in = fruits[right];
            if (hash[in] == 0) kinds++; // 维护水果种类
            hash[in]++; // 进窗口

            // 判断
            while (kinds > 2) {
                int out = fruits[left];
                hash[out]--; // 出窗口
                if (hash[out] == 0) kinds--; // 维护水果种类
                left++;
            }

            // 更新结果
            ret = Math.max(ret, right - left + 1);
        }
        return ret;
    }
}
